package q1022_sumRootToLeaf;

import CommonClass.Common.TreeNode;

public class Solution_1 {
    int sumVal = 0;
    int path = 0;
    public int sumRootToLeaf(TreeNode root) {
        dfs(root);
        return sumVal;
    }

    /*
    此题的思路是利用path记录每条路径的值 然后用sum来累加
    采用回溯做法的关键在于 需要每次进入dfs后将path回滚 避免导致之后的回溯出现错误
     */
    private void dfs(TreeNode root) {
        if (root.left == null && root.right == null){
            sumVal += root.val + path;
            return;
        }

        path += root.val;

        if (root.left != null) {
            path = path << 1;
            dfs(root.left);
            path = path >> 1;
        }
        if (root.right != null) {
            path = path << 1;
            dfs(root.right);
            path = path >> 1;
        }

    }
}
